package leetcode.code994.RottingOranges;

import leetcode.helper.HelpDebug;

/**
 * 01矩阵方式
 * @author Administrator
 *
 */
public class Solution99402 extends RottingOranges {

	@Override
	public int orangesRotting(int[][] grid) {
		int h = grid.length;
		int w = grid[0].length;
		int range = h*w;
		int[][] res = new int[h][w];
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (grid[i][j] == 2)
					res[i][j] = 0;
				else if (grid[i][j] == 1)
					res[i][j] = range;
				else
					res[i][j] = -1;
			}
		}
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (i - 1 >= 0 && res[i - 1][j] != -1)
					res[i][j] = Math.min(res[i][j], res[i - 1][j] + 1);
				if (j - 1 >= 0 && res[i][j - 1] != -1)
					res[i][j] = Math.min(res[i][j], res[i][j - 1] + 1);
			}
		}
		System.out.println("--1--");
		HelpDebug.printArray2(res);
		System.out.println("--2--");
		int numMax = 0;// 最大天数
		for (int i = h - 1; i >= 0; i--) {
			for (int j = w - 1; j >= 0; j--) {
				if (i + 1 < h && res[i + 1][j] != -1)
					res[i][j] = Math.min(res[i][j], res[i + 1][j] + 1);
				if (j + 1 < w && res[i][j + 1] != -1)
					res[i][j] = Math.min(res[i][j], res[i][j + 1] + 1);
//				if(res[i][j] == range)
//					return -1;
				numMax = Math.max(numMax, res[i][j]);
			}
		}
		System.out.println("--3--");
		HelpDebug.printArray2(res);
		System.out.println("--4--");
		return numMax == range ? -1 : numMax;
	}

	public static void main(String[] args) {
		Solution99402 so = new Solution99402();
//		so.debug1();
//		so.debug2();
//		so.debug3();
		so.debug4();
	}

}
